package algorithm;

import java.util.List;

public class leetcode_0120 {
    public int minimumTotal(List<List<Integer>> triangle) {
        int len=triangle.size();
        int [][] dp=new int[len][len];
        dp[0][0]=triangle.get(0).get(0);
        for(int i=1;i<len;++i){
            dp[i][0]=triangle.get(i).get(0)+dp[i-1][0];
            dp[i][i]=dp[i-1][i-1]+triangle.get(i).get(i);
        }
        for(int i=1;i<len;++i){
            for(int j=1;j<i;++j){
                dp[i][j]=triangle.get(i).get(j)+Math.min(dp[i-1][j-1],dp[i-1][j]);
            }
        }
        int min=dp[len-1][0];
        for(int i=0;i<len;++i){
            min=Math.min(dp[len-1][i],min);
        }
        return min;
    }
}
